#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点数据结构ListNode
typedef struct ListNode{
  int data; // 数据域
  struct ListNode *next; // 指针域，指向下一个节点
} Node;

// 定义单链表数据结构LinkedList
typedef struct{
  Node *head; // 链表头指针成员
  size_t size; // 链表中节点个数
} LinkedList;

/**
 * @brief 初始化单链表
 * @param 要初始化的单链表指针
 * @return 无
 */
void initLinkedList(LinkedList *list){
  // 初始化头指针
  list->head=NULL; // 防止野指针
  list->size=0;
}
/**
 * @brief 获取单链表长度(元素个数)
 * @param 单链表指针
 * @return 无
 */
size_t getSize(LinkedList *list){
  return list->size;
}
/**
 * @brief 在指定位置插入新
 * @param index 要插入的位置
 * @param element 要插入的新元素
 * @return 无
 */
void insertAt(LinkedList *list, size_t index, int element){
  // 忽略错误位置
  if(index>list->size||index<0){
    printf("要插入的位置无效");
    return; 
  }
  // 创建新节点
  Node *newNode = malloc(sizeof(Node));
  newNode->data = element;
  // 找到要插入的位置
  if(index==0){//在头部
    newNode->next=list->head; // 挂链
    list->head = newNode; // 更新新节点为链表的头
  }else{// 其他位置-中间或尾部
    // 复制头指针（因为不能动头指针），然后使用复制后的辅助指针进行操作
    Node *tempNode = list->head;
    for(int i=0;i<index-1;i++){
      tempNode = tempNode->next;
    }
    // 执行插入操作
    newNode->next = tempNode->next;// 挂链
    tempNode->next = newNode;
  }
  list->size++; // 更新节点数数量
}

/**
 * @brief 在尾部插入新元素
 * @param element 要插入的新元素
 * @return 无
 */
void insertTail(LinkedList *list, int element){
  insertAt(list,list->size,element);
}

/**
 * @brief 删除指定位置的元素
 * @param index 要删除的位置
 * @return int 返回被删除的元素值
 */
int removeAt(LinkedList *list, size_t index){
  // 忽略错误位置
  if(index>=list->size||index<0){
    printf("要删除的位置无效");
    return -1; 
  }
  int removedElement=0; // 保存要删除的元素值
  Node *tempNode = list->head; // 指向头部的辅助指针
  if(index==0){ // 删除头节点
    // 先移动头节点到新的位置
    list->head = tempNode->next;
    // 删除旧头前，先保存它的数据
    removedElement = tempNode->data;
    free(tempNode); // 最后再删除旧头
  }else{// 删除非头节点
    // 将辅助指针移动到要删除节点的前一个位置
    for(int i=0;i<index-1;i++){
      tempNode = tempNode->next;
    }
    // 先保存要删除的节点地址，因为等会要free它
    Node *removeNode = tempNode->next;
    removedElement = removeNode->data;
    tempNode->next = tempNode->next->next; // 挂链
    removeNode->next = NULL; // 摘链
    free(removeNode); // 释放被删除节点的空间
  }
  list->size--; // 更新元素个数
  return removedElement;  
}

/**
 * @brief 删除尾节点
 * @return int 返回被删除的元素值
 */
int removeTail(LinkedList *list){
  removeAt(list,list->size-1);
}

/**
 * @brief 获取指定位置的元素值
 * @param list 指定的链表地址
 * @param index 指定的位置
 * @return 无
 */
int getElementAt(LinkedList *list, size_t index){
  if(index>=list->size|index<0){
    printf("指定位置无效");
    return -1;
  }
  Node *tempNode = list->head;
  // 移动指针到指定位置
  for(int i=0;i<index;i++){
    tempNode = tempNode->next;
  }
  return tempNode->data;
}

/**
 * @brief 删除链表
 * @param list 要删除链表的指针
 * @return 无
 */
void destroyLinkedList(LinkedList *list){
  // 不能直接删除链表，因为还有链表的节点们散落在堆内存空间
  // 依次先从单链表头部开始释放节点
  Node *tempNode = list->head;
  Node *removeNode = NULL;
  while (tempNode!=NULL) { // 还没释放到结尾
    // 先保存要删除的头
    removeNode = tempNode;
    // 然后找到下一个头
    tempNode = tempNode->next;
    // 删除当前的头部
    removeNode->next=NULL;
    free(removeNode);
  }
  // 所有的头删除完毕后, 最后释放单链表
  list->head=NULL;    
  list->size=0;
}


int main(void){
  // 定义一个单链表
  LinkedList list;
  // 初始化单链表
  initLinkedList(&list);
  // 插入新元素
  insertAt(&list,0,1);
  insertAt(&list,0,2);
  insertAt(&list,0,3);
  // 中间位置插入
  insertAt(&list,1,4); 
  // 尾部插入
  insertTail(&list,5); 

  // 删除头部
  removeAt(&list,0);
  // 删除指定位置
  removeAt(&list,2);
  // 删除尾部
  removeTail(&list);

  printf("头节点的值：%d\n",getElementAt(&list,0));

  // 最后释放单链表空间
  destroyLinkedList(&list);
  return 0;
}
